4.1 Priority Queues (priority_queue)

priority_queue K I

1. Definition

An instance Q of the parameterized data type is a collection of items (type pq$\_item$). Every item contains a key from type K and an information from the linearly ordered type I. K is called the key type of Q and I is called the information type of Q. The number of items in Q is called the size of Q. If Q has size zero it is called the empty priority queue. We use < k, i > to denote a pq$\_item$ with key k and information i.


2. Creation

a) Q

b) $\_priority$$\_queue$< K, I, prio$\_impl$> Q;

creates an instance of type and initializes it with the empty priority queue. Variant a) chooses the default data structure (cf. 4.1.4), and variant b) chooses class prio$\_impl$ as the implementation of the queue (cf. section 9 for a list of possible implementation parameters).


3. Operations

& truecm & truecm & K key pq_item it returns the key of item it. it is an item in .

I inf pq_item it returns the information of item it. it is an item in .

pq_item insert K k,I i adds a new item < k, i > to and returns it.

pq_item find_min returns an item with minimal information (nil if is empty)

void del_item pq_item it removes the item it from . it is an item in .

K del_min removes the item it = .find_min() from and returns the key of it. is not empty.

void decrease_inf pq_item it, I i makes i the new information of item it it is an item in and i is not larger then inf (it).

void change_key pq_item it, K k makes k the new key of item it it is an item in .

void clear makes the empty priority queue

bool empty returns true, if is empty, false otherwise

int size returns the size of .


4. Implementation

Priority queues are implemented by Fibonacci heaps ([FT84]. Operations insert, del_item, del_min take time O(log n), find_min, decrease_inf, key, inf, empty take time O(1) and clear takes time O(n), where n is the size of . The space requirement is O(n).


5. Example

Dijkstra's Algorithm (cf. section 8.1)